package vip.zhenzicheng.algorithm.leetcode.binary_tree;

import vip.zhenzicheng.algorithm.TreeNode;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/validate-binary-search-tree/">验证二叉搜索树 [中等]</a>
 *
 * @author zhenzicheng
 * @date 2022-06-27 10:52
 */
public class ValidateBinarySearchTree_98 {

  /*递归*/
  public boolean isValidBST(TreeNode root) {
    return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); // 初始默认区间为[-无穷,无穷]
  }

  public boolean isValidBST(TreeNode root, long minVal, long maxVal) {
    // 递归终止条件，本身null或已经递归到了叶子节点
    if (root == null) {
      return true;
    }
    // 不满足二叉搜索树定义
    if (root.val >= maxVal || root.val <= minVal) {
      return false;
    }
    // 递归判断所有左子树的节点值的范围应该在[-无穷, root.val],右子树节点值的范围应该在[root.val, 无穷]
    return isValidBST(root.left, minVal, root.val) && isValidBST(root.right, root.val, maxVal);
  }

  /*基于中序遍历*/
  public boolean isValidBSTInOrderWithStack(TreeNode root) {
    if (root == null) return true;
    Deque<TreeNode> stack = new LinkedList<>();
    // 用来存储前一个节点的值
    TreeNode pre = null;
    while (root != null || !stack.isEmpty()) {
      while (root != null) {
        stack.push(root);
        root = root.left;
      }
      root = stack.pop();
      // 不满足定义
      if (pre != null && root.val <= pre.val) {
        return false;
      }
      pre = root;
      root = root.right;
    }
    return true;
  }

}
